public class BinarySearchTree {
    public static class Node{
        int key;
        Node left;
        Node right;
        public Node(int key){
            this.key = key;
        }
    }
    private Node root=null;
    //在搜索树中查找 key，如果找到，返回 key 所在的结点，否则返回 null
    public Node search(int key){
        Node cur=root;
        while (cur!=null){
            if (key==cur.key){
                return cur;
            }else if(key< cur.key){
                cur=cur.left;
            }else {
                cur=cur.right;
            }
        }
        return null;
    }
    //插⼊
    public boolean insert(int key){
        if (root==null){
            root=new Node( key);
            return true;
        }
        Node cur=root;
        Node parent=null;
        while (cur!=null){
            if (key==cur.key){
                return false;
            }else if (key<cur.key){
                parent=cur;
                cur=cur.left;
            }else {
                parent=cur;
                cur=cur.right;
            }
        }
        Node node=new Node(key);
        if (key<parent.key){
            parent.left=node;
        }else {
            parent.right=node;
        }
        return true;
    }
    //删除成功返回 true，失败返回 false
    public boolean remove(int key){
        Node cur=root;
        Node parent=null;
        while (cur!=null){
            if (key==cur.key){
                break;
            }else if (key<cur.key){
                parent=cur;
                cur=cur.left;
            }else {
                parent=cur;
                cur=cur.right;
            }
        }
        //该元素不在二叉搜索树中
        if (cur==null){
            return false;
        }
        /*
        根据cur的孩⼦是否存在分四种情况
        1. cur左右孩⼦均不存在
        2. cur只有左孩⼦
        3. cur只有右孩⼦
        4. cur左右孩⼦均存在
        */
        //有两个子节点
        if (cur.left!=null && cur.right!=null){
            //找到右子树额最小节点
            Node successor=cur.right;
            Node successorParent=cur;
            while (successor.left!=null){
                successorParent=successor;
                successor=successor.left;
            }
            // 将后继节点的值复制到当前节点
            cur.key = successor.key;
            // 接下来删除后继节点（它最多只有一个右子节点）
            cur=successor;
            parent=successorParent;
        }
        // 此时 cur 最多只有一个子节点
        Node child;
        if (cur.left != null) {
            child = cur.left;
        } else {
            child = cur.right;
        }
        // 情况2：删除的是根节点
        if (parent == null) {
            root = child;
        }
        // 情况3：不是根节点，根据 cur 是 parent 的左还是右孩子来更新指针
        else if (parent.left == cur) {
            parent.left = child;
        } else {
            parent.right = child;
        }

        return true;
    }
}
